package it.luigiarpino.kernighanLin;

import java.util.Random;



public class BiPartition 
{

	private int[][] matrix;
	private int[] partitionA;
	private int[] partitionB;
	private int costo;
	
	
	public BiPartition(int[][] matrix)
	{
		this.matrix=matrix;
		this.partitionA=null;
		this.partitionB=null;
		this.costo=-1;
		this.getBipartition();
	}
	
	private void getBipartition()
	{
		int numIterazioniNonMigliorative=0;
		while ( numIterazioniNonMigliorative < 10 )
		{
			int[][] part=this.getRandomPartition();
			int[][] result=getPartition(part[0],part[1]);
			int[] partA=result[0];
			int[] partB=result[1];
			int costoAttuale=this.getCostoTotale(partA, partB);
			if (this.partitionA==null || costoAttuale<costo)
			{
				this.costo=costoAttuale;
				this.partitionA=partA;
				this.partitionB=partB;
				numIterazioniNonMigliorative=0;
			}
			else
			{
				numIterazioniNonMigliorative ++;
			}
		}
		
	}
	
	private int[][] getPartition( int[]partitionA, int[]partitionB)
	{
		int[] partA=partitionA;
		int[] partB=partitionB;
		boolean isTerminated=false;
		while ( !isTerminated )
		{
			int[] result = getSwapNode( partA, partB);
			int nodoA=result[0];
			int nodoB=result[1];
			int guadagno=result[2];
			if (guadagno >0)
			{
				partA=changeNodes(partA, nodoA, nodoB);
				partB=changeNodes(partB, nodoB, nodoA);
			}
			else
			{
				isTerminated=true;
			}
		}
		return new int[][]{ partA, partB  };
	}
	
	private static int[] changeNodes(int[]partition, int oldNode, int newNode )
	{
		for(int i=0 ; i<partition.length ; i++)
		{
			if (partition[i]==oldNode)
			{
				partition[i]=newNode;
			}
		}
		return partition;
	}
	
	private int[] getSwapNode(  int[]partitionA, int[]partitionB)
	{
		// calcolo D per tutti i nodi
		int[] D=new int[matrix.length];
		for (int i=0 ; i<matrix.length ; i++)
		{
			D[i]=getD( i, partitionA, partitionB);
		}
		// calcolo la matrice dei  guadagni
		int nodoPartA=-1;
		int nodoPartB=-1;
		int maxGuadagno=0;
		for (int i=0 ; i <partitionA.length ; i++)
		{
			for(int j=0 ; j< partitionB.length ; j++ )
			{
				int a=partitionA[i];
				int b=partitionB[j];
				int guadagno=D[a]+D[b]-( 2 * matrix[a][b] );
				/*
				System.out.println("Scambio "+a+" con "+b+" con guadagno="+guadagno);
				System.out.println("Wab="+matrix[a][b]);
				System.out.println("D[a]="+D[a]);
				System.out.println("D[b]="+D[b]);
				System.out.println();
				*/
				if (guadagno>maxGuadagno)
				{
					nodoPartA=a;
					nodoPartB=b;
					maxGuadagno=guadagno;
				}
			}
		}
		
		return new int[]{nodoPartA, nodoPartB, maxGuadagno };
	}
	
	
	
	
	private int[][] getRandomPartition()
	{
		int[] partA=new int[matrix.length/2];
		int[] partB=new int[matrix.length/2];
		if (this.partitionA==null)
		{
			for(int i=0 ; i<matrix.length/2;i++)
			{
				partA[i]=i;
				partB[i]=(matrix.length/2)+i;
			}
		}
		else
		{
			Random rand=new Random();
			int indice=rand.nextInt( matrix.length );
			for(int i=0; i<partA.length; i++)
			{
				if (i<indice)
				{
					partA[i]=this.partitionA[i];
					partB[i]=this.partitionB[i];
				}
				else
				{
					partA[i]=this.partitionB[i];
					partB[i]=this.partitionA[i];
				}
			}
		}
		return new int[][]{ partA, partB};
	}
	
	private int getD( int element,int[]partitionA, int[]partitionB)
	{
		int costoEsterno=0;
		int costoInterno=0;
		if ( isIn(element, partitionA) )
		{
			for(int i=0 ; i < partitionB.length ; i++)
			{
				costoEsterno += matrix[element][partitionB[i]];
			}
			for (int i=0;i< partitionA.length ;i++)
			{
				costoInterno+= matrix[element][partitionA[i]];
			}
		}
		else
		{
			for(int i=0 ; i < partitionA.length ; i++)
			{
				costoEsterno += matrix[element][partitionA[i]];
			}
			for (int i=0;i< partitionB.length ;i++)
			{
				costoInterno+= matrix[element][partitionB[i]];
			}
		}
		/*
		System.out.println("element="+element);
		System.out.println("costoEsterno="+costoEsterno);
		System.out.println("costoInterno="+costoInterno);
		*/
		return costoEsterno-costoInterno;
	}
	
	private boolean isIn(int element, int[]partition )
	{
		for(int i=0 ; i<partition.length ; i++)
		{
			if ( element==partition[i])
			            return true;
		}
		return false;
	}
	
	/**
	 * Funzione di utilità by Luigi
	 * @param matrix
	 * @param element
	 * @param partitionA
	 * @param partitionB
	 * @return
	 */
	private int getCostoTotale( int[]partitionA, int[]partitionB)
	{
		int costo = 0;
		for (int i=0 ; i <partitionA.length ; i++)
		{
			for(int j=0 ; j< partitionB.length ; j++ )
			{
				int a=partitionA[i];
				int b=partitionB[j];
				int wab=matrix[a][b];
				costo += wab; 
			}
		}
		return costo;
	}
	
	
	public static void main(String[] args)
	{
		/*
		int[][] matrix={
			    //   0  1  2  3  4  5  6  7
					{0, 0, 1, 0, 0, 0, 0, 0 },// 0
					{0, 0, 1, 0, 0, 0, 0, 0 },// 1
					{1, 1, 0, 1, 1, 0, 0, 0 },// 2
					{0, 0, 1, 0, 0, 0, 0, 0 },// 3
					{0, 0, 1, 0, 0, 1, 1, 1 },// 4
					{0, 0, 0, 0, 1, 0, 0, 0 },// 5
					{0, 0, 0, 0, 1, 0, 0, 0 },// 6
					{0, 0, 0, 0, 1, 0, 0, 0 },// 7
			};
		*/
		
		int[][] matrix={
			   //0  1  2  3  4  5  6  7
				{0, 0, 1, 0, 0, 0, 0, 0 },// 0
				{0, 0, 0, 1, 0, 0, 0, 0 },// 1
				{1, 0, 0, 1, 1, 0, 1, 0 },// 2
				{0, 1, 1, 0, 0, 1, 0, 0 },// 3
				{0, 0, 1, 0, 0, 1, 0, 0 },// 4
				{0, 0, 0, 1, 1, 0, 0, 1 },// 5
				{0, 0, 1, 0, 0, 0, 0, 0 },// 6
				{0, 0, 0, 0, 0, 1, 0, 0 },// 7
		};
		BiPartition biPartition=new BiPartition(matrix);
		int[]partA=biPartition.getPartitionA();
		int[]partB=biPartition.getPartitionB();
		int costoFinale=biPartition.getCosto();

		System.out.println("\n\nCosto Finale="+ costoFinale );
		System.out.print("PartA=");
		for(int i=0 ; i<partA.length ; i++)
		{
			System.out.print(" "+partA[i]);
		}
		System.out.print("\nPartB=");
		for(int i=0 ; i<partB.length ; i++)
		{
			System.out.print(" "+partB[i]);
		}
	}

	public int[] getPartitionA() {
		return partitionA;
	}

	public int[] getPartitionB() {
		return partitionB;
	}

	public int getCosto() {
		return costo;
	}
}
